package java学习.leetcode.editor.cn;

import java.util.Stack;

/**
 * @author 刘世锦
 * 2022-11-09 23:44:19	 当前时间
 */
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 每个右括号都有一个对应的相同类型的左括号。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()"
//输出：true
// 
//
// 示例 2： 
//     0   2   4
//  ( [ { } ] )

/**
 *
 *  0 1 2 3 4 5
 * 	( [ { } ] )
 *    [   }   )
 *  (   {   ]
 *
 */

//输入：s = "()[]{}"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：s = "(]"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 仅由括号 '()[]{}' 组成 
//            ) ] }
// Related Topics 栈 字符串 
// 👍 3598 👎 0

public class 有效的括号{
	public static void main(String[] args) {
		Solution solution = new 有效的括号().new Solution();
//		String s = "()[]{}";
		String s = " ){";

		System.out.println(solution.isValid(s));
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//输入：s = "()[]{}"
//输出：true
//
//
// 示例 3：
//
//
//输入：s = "(]"
//输出：false

/**
 *         i
 *   ( ) [ ] { }
 * | ]
 */
	/**
	 * 1. 当s遍历到 ( [ { 时，每次压栈另一半： ) } ]
	 * 2. s遍历到另一半时，开始出栈比较和非空验证
	 * 		非空验证是因为可能出现多余的字符串 eg： （{[]}))()
	 * 3. 若s遍历结束 则判断stack是否为空
	 */
	public boolean isValid(String s) {

		Stack<Character> stack = new Stack<Character>();
		for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
//			System.out.println(stack);
			if (ch=='{'){
				stack.push('}');
			} else if (ch=='['){
				stack.push(']');
			} else if (ch=='('){
				stack.push(')');
			}else if (stack.isEmpty()||stack.peek()!=ch){
				return false;
			}else{
				stack.pop();
			}
		}
		return stack.isEmpty();
	}
	public boolean isValid2(String s) {
		Stack<Character>stack = new Stack<Character>();
		for(char c: s.toCharArray()){
			if(c=='(') {
				stack.push(')');
			} else if(c=='[') {
				stack.push(']');
			} else if(c=='{') {
				stack.push('}');
			} else if(stack.isEmpty()||c!=stack.pop()) {
				return false;
			}
		}
		return stack.isEmpty();
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
